from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]  # matrix视作 N*N 的平面坐标矩阵
        x0 = y0 = 0  # x轴左边界和y轴上边界
        x1 = y1 = n - 1  # x轴右边界和y轴下边界

        i = j = 0  # 当前的游标

        acc = 0  # 累加器
        x_step = 1  # x轴步进单元，正数1为向右，负数-1为向左
        y_step = 1  # y轴步进单元，正数1为向下，负数-1为向上

        while 0 <= x0 <= i <= x1 < n:
            if x_step > 0:  # 当前x轴方向从左向右
                if i < x1:
                    # 从左到右填充特定一行的数值
                    matrix[j][i] = acc = acc + 1
                elif i == x1:
                    # 从上到下填充特定一列的数值
                    while 0 <= y0 <= j <= y1 < n:
                        matrix[j][i] = acc = acc + 1
                        if j == y1:
                            break
                        j += y_step

                    # 填充完一列:

                    # 修改x/y轴步进方向，改为从右向左
                    x_step = -1
                    y_step = -1

                    # 压缩x右边界，y上边界
                    y0 += 1
                    x1 -= 1
            else:  # 当前x轴方向从右向左
                if i > x0:
                    # 从右到左填充特定一行的数值
                    matrix[j][i] = acc = acc + 1
                elif i == x0:
                    # 从下到上填充特定一列的数值
                    while 0 <= y0 <= j <= y1 < n:
                        matrix[j][i] = acc = acc + 1
                        if j == y0:
                            break
                        j += y_step

                    # 填充完一列:

                    # 修改x/y轴步进方向，改为从左向右
                    x_step = 1
                    y_step = 1

                    # 压缩y下边界，x左边界
                    y1 -= 1
                    x0 += 1

            i += x_step

        return matrix


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    ret = Solution().generateMatrix(3)
    print(ret)
